home *** CD-ROM | disk | FTP | other *** search
- #pragma once
-
- #ifndef __LISTTEMPLATE__
- #define __LISTTEMPLATE__
-
- #define DEBUGPREEMPTIVELOCK 1
-
- //
- // For 'nil'
- //
- #include <Types.h>
-
- //
- // This is how many elements our list grows by every time we run
- // out of space. We could potentially be a lot more intelligent
- // about our growing behavior.
- //
- // n.b. Currently these lists never trim, which could be bad.
- //
- #define kAllocationChunk 32
-
- //
- // We usually don't have more than two iterators on a list, so
- // we'll only allocate space for the iterator list two elements
- // at a time.
- //
- #define kIterListAllocationChunk 2
-
- typedef Boolean (*ListElementCompareProcPtr)(const char* item1, const char* item2);
-
-
- class TAbstractListIterator;
-
- //================================================================================
- // CLASS TListStorage
- //
- // This class is for use by the list template, and isn't intended for direct use.
- //================================================================================
-
- class TListStorage
- {
- //
- // Only TAbstractListIterators may add or remove themselves
- // to our iterator list
- //
- friend class TAbstractListIterator;
-
- public:
- TListStorage(UInt32 itemSize) :
- fListData(nil),
- fItemSize(itemSize),
- fItemsInList(0),
- fSpaceReserved(0),
- #if DEBUGPREEMPTIVELOCK
- fReadLocks(0),
- fWriteLocks(0),
- #endif
- fIteratorList(nil),
- fNumberOfIterators(0),
- fIteratorListReservedSpace(0) {}
-
- TListStorage(UInt32 itemSize, UInt32 initialItemSpace) :
- fListData(nil),
- fItemSize(itemSize),
- fItemsInList(0),
- fSpaceReserved(0),
- #if DEBUGPREEMPTIVELOCK
- fReadLocks(0),
- fWriteLocks(0),
- #endif
- fIteratorList(nil),
- fNumberOfIterators(0),
- fIteratorListReservedSpace(0) { this->InsureAdequateSpace(initialItemSpace); }
-
- TListStorage(const TListStorage& copyFrom);
-
- ~TListStorage();
-
- //
- // Simple list access
- //
- Boolean Empty() const { return (this->ItemsInList() == 0); }
- UInt32 ItemsInList() const { return fItemsInList; }
-
- //
- // Primary list-manipulation and item access API:
- //
- TListStorage* Clone() const;
-
- //
- // Add an item to the list in no particular order (puts new
- // item in using the fastest insertion available)
- //
- void Add(const char* elementAddress);
- Boolean Remove(const char*, ListElementCompareProcPtr compareProc);
-
- //
- // n.b. Inserting N items at the beginning of the list is O(N^2)
- // Inserting N items at the end of the list is O(N)
- // Inserting N items at the end of the list and reversing their order is also O(N).
- //
- void InsertAtBeginning(const char* elementAddress);
- void InsertAtEnd(const char* elementAddress);
-
- //
- // n.b. Removing N items from the beginning of the list is O(N^2)
- // Removing N items from the end of the list is O(N)
- //
- void RemoveFromBeginning();
- void RemoveFromEnd();
-
- //
- // List accessors
- //
- void FirstItem(char* copyToBuffer) const;
- void LastItem(char* copyToBuffer) const;
-
- //
- // Misc list manipulation
- //
- void ReverseOrderOfList(char* tempBuffer);
- void MakeEmpty();
-
- //
- // Access locks for preemptive software (see comment below)
- //
- void LockForReading() const;
- void RelinquishReadLock() const;
- void LockForWriting();
- void RelinquishWriteLock();
-
- //
- // Not preemptive-safe if called directly; however, ONLY
- // these routines + the "simple list access" routines may
- // be called if you explicitly lock a list for writing.
- //
- // If you explicitly lock a list for reading, it is okay
- // to call 'const' routines from above, but don't call any
- // routines that try to write, or you'll deadlock.
- //
- void ItemAtIndex(SInt32 itemIndex, char* copyToBuffer) const;
- void ReplaceItemAtIndex(SInt32 itemIndex, const char* dataToReplaceWith);
- void RemoveItemAtIndex(SInt32 itemIndex);
- SInt32 IndexOfItem(const char*, ListElementCompareProcPtr compareProc, SInt32 indexToStartAt = 0) const;
-
- private:
-
- //
- // Memory handling
- //
- void InsureAdequateSpace(SInt32 numberOfItems);
-
- //
- // Peeking at items:
- //
- const char* ItemAddress(SInt32 itemIndex) const { return this->fListData + (itemIndex * fItemSize); }
- char* ItemAddress(SInt32 itemIndex) { return this->fListData + (itemIndex * fItemSize); }
-
- //
- // Keeping iterators in sync:
- //
- void AddIterator(TAbstractListIterator*);
- void RemoveIterator(TAbstractListIterator*);
- void InsureSpaceForIteratorList(UInt16 numberOfItersNeeded);
-
- void NotifyItemAdded(SInt32 indexOfNewItem);
- void NotifyItemRemoved(SInt32 indexOfItemRemoved);
- void NotifyListDestroyed();
-
- private:
- char* fListData;
- UInt32 fItemSize;
- UInt32 fItemsInList;
- UInt32 fSpaceReserved;
-
- #if DEBUGPREEMPTIVELOCK
- UInt32 fReadLocks;
- UInt32 fWriteLocks;
- #endif
-
- TAbstractListIterator** fIteratorList;
- UInt16 fNumberOfIterators;
- UInt16 fIteratorListReservedSpace;
- };
-
- template <class T> class AnIteratorOfAListOf;
-
- //================================================================================
- // TEMPLATE AListOf
- //================================================================================
-
- template <class T> class AListOf
- {
- //
- // This is only here so that the iterator can gain access to the
- // list storage object durring its constructor and destructor,
- // and thereby register itself with the list storage.
- //
- friend class AnIteratorOfAListOf<T>;
-
- public:
- AListOf() :
- fListStorage(sizeof(T)) {}
-
- AListOf(SInt32 initialItems) :
- fListStorage(sizeof(T), initialItems) {}
-
- AListOf(const AListOf<T>& copyFrom) :
- fListStorage(copyFrom.fListStorage) {}
-
- //
- // Simple list access
- //
- Boolean Empty() const { return fListStorage.Empty(); }
- SInt32 ItemsInList() const { return fListStorage.ItemsInList(); }
-
- //
- // Primary list-manipulation and item access API:
- //
- AListOf<T>* Clone() const { AListOf<T>* clonedList = new AListOf<T>(*this); return clonedList; }
-
- //
- // Add an item to the list in no particular order (puts new
- // item in using the fastest insertion available)
- //
- void Add(const T& valueToAdd) { fListStorage.Add((const char*)&valueToAdd); }
- Boolean Remove(const T& valueToRemove) { return fListStorage.Remove((const char*)&valueToRemove, CompareTwoElements); }
-
- //
- // n.b. Inserting N items at the beginning of the list is O(N^2)
- // Inserting N items at the end of the list is O(N)
- // Inserting N items at the end of the list and reversing their order is also O(N).
- //
- void InsertAtBeginning(const T& valueToAdd) { fListStorage.InsertAtBeginning((const char*)&valueToAdd); }
- void InsertAtEnd(const T& valueToAdd) { fListStorage.InsertAtEnd((const char*)&valueToAdd); }
-
- //
- // n.b. Removing N items from the beginning of the list is O(N^2)
- // Removing N items from the end of the list is O(N)
- //
- void RemoveFromBeginning() { fListStorage.RemoveFromBeginning(); }
- void RemoveFromEnd() { fListStorage.RemoveFromEnd(); }
-
- //
- // List accessors
- //
- T FirstItem() const { T result; fListStorage.FirstItem((char*)&result); return result; }
- T LastItem() const { T result; fListStorage.LastItem((char*)&result); return result; }
-
- //
- // Misc list manipulation
- //
- void ReverseOrderOfList() { T tempStorage; fListStorage.ReverseOrderOfList((char*)&tempStorage); }
- void MakeEmpty() { fListStorage.MakeEmpty(); }
-
- //
- // Synonyms, for those who care
- //
- void Push(const T& valueToPush) { this->InsertAtEnd(valueToPush); }
- T TopOfStackValue() const { return this->LastItem(); }
- T Pop() { T temp = this->TopOfStackValue(); this->RemoveFromEnd(); return temp; }
-
- //
- // Enqueueing and dequeueing N items is O(N*D), where D is the
- // average depth of the queue. This is O(N^2) for most uses.
- // O(N) algorithms exist, but currently are not implemented, as
- // they require leaving insertion gaps that either invalidate the
- // format of our list, or needlessly complicate the access for
- // all lists, even those not to be used as a queue. If you
- // really need a fast queue, write a queue class, don't use this
- // template.
- //
- void Enqueue(const T& valueToQ) { this->InsertAtEnd(valueToQ); }
- T TopOfQueueValue() const { return this->FirstItem(); }
- T Dequeue() { T temp = this->TopOfQueueValue(); this->RemoveFromBeginning(); return temp; }
-
- //
- // Access locks for preemptive software.
- //
- // These locks should be kept for a minimum amount of time.
- // Note that the methods above all call Lock/Relinquish as
- // necessary.
- //
- // - LockForReading blocks until the active writer (if any)
- // relinquishes the write lock
- // - LockForWriting blocks until the active writer and all
- // active readers (if any) relinquish their respective locks
- //
- // Every call to "Lock" must be (soon) balanced by a call to
- // "Relinquish"; calling LockForReading multiple times is okay,
- // as long as the calls to RelinquishReadLock balance the calls
- // to LockForReading.
- //
- // IMPORTANT: There can only be one writer, so you will
- // block yourself forever (deadlock) if you try to LockForWriting.
- // twice. You will also block yourself forever if you call
- // LockForWriting followed by a call to LockForReading (or
- // visa-versa).
- //
- // Therefore, calling the Lock routines directly is dangerous
- //
- void LockForReading() const { fListStorage.LockForReading(); }
- void RelinquishReadLock() const { fListStorage.RelinquishReadLock(); }
- void LockForWriting() { fListStorage.LockForWriting(); }
- void RelinquishWriteLock() { fListStorage.RelinquishWriteLock(); }
-
- //
- // WARNING: The following routines are not pre-emptive safe if called directly,
- // because the index values may change at any instant if another task
- // modifies the list.
- //
- // Pre-emptive-safe alternatives:
- //
- // ItemAtIndex: use an iterator and iter.Current()
- // ReplaceItemAtIndex: use an iterator and iter.SetCurrent()
- // RemoveItemAtIndex: use an iterator and iter.RemoveCurrent()
- // IndexOfItem: use an iterator and iter.AdvanceToItem()
- //
- // If for some reason you have a burning desire to NOT use an
- // iterator, you may call these routines if you Lock/Relinquish
- // this list appropriately, but you must do so carefully if you
- // want to avoid deadlock.
- //
- T ItemAtIndex(SInt32 itemIndex) const { T result; fListStorage.ItemAtIndex(itemIndex, (char*)&result); return result; }
- void ReplaceItemAtIndex(SInt32 itemIndex, const T& newValue) { fListStorage.ReplaceItemAtIndex(itemIndex, (char*)&newValue); }
- void RemoveItemAtIndex(SInt32 itemIndex) { fListStorage.RemoveItemAtIndex(itemIndex); }
- SInt32 IndexOfItem(const T& itemToFind, SInt32 startAt = 0) const { return fListStorage.IndexOfItem((const char*)&itemToFind, CompareTwoElements, startAt); }
-
- protected:
- static Boolean CompareTwoElements(const char* item1, const char* item2);
-
- //
- // The ListStorage accessor is only used by AnIteratorOfAListOf
- // to get the list storage to register itself with the list
- // storage.
- //
- TListStorage& ListStorage() { return fListStorage; }
-
- private:
- TListStorage fListStorage;
- };
-
-
- //-------------------------------------------------------------------
- // AListOf<T>::CompareTwoElements
- //-------------------------------------------------------------------
- template <class T>
- Boolean AListOf<T>::CompareTwoElements(const char* item1, const char* item2)
- {
- return ((T*)item1) == ((T*)item2);
- }
-
-
- //================================================================================
- // CLASS TAbstractListIterator
- //
- // Abstract base class for iterators, so that we may keep track of our
- // iterators in our list-storage class.
- //================================================================================
-
- class TAbstractListIterator
- {
- public:
- virtual void NotifyItemAdded(SInt32 indexOfNewItem) = 0;
- virtual void NotifyItemRemoved(SInt32 indexOfItemRemoved) = 0;
- virtual void NotifyListDestroyed() = 0;
-
- protected:
- void RegisterWithList(TListStorage& list) { list.AddIterator(this); }
- void UnregisterWithList(TListStorage& list) { list.RemoveIterator(this); }
- };
-
- //================================================================================
- // TEMPLATE AnIteratorOfAListOf
- //================================================================================
-
- template <class T> class AnIteratorOfAListOf : public TAbstractListIterator
- {
- public:
- AnIteratorOfAListOf(AListOf<T>* inList, Boolean iterateBackwards = false) :
- fList(inList),
- fCurrentItem(0),
- fRemovedCurrent(false),
- fWeRemovedCurrent(false),
- fIterateBackwards(iterateBackwards) { this->RegisterWithList(fList->ListStorage()); this->Reset(iterateBackwards); }
-
- ~AnIteratorOfAListOf() { this->UnregisterWithList(fList->ListStorage()); }
-
- void Reset(Boolean iterateBackwards = false);
-
- Boolean More() const;
- UInt32 ItemsRemainingToIterate() const;
- void Next();
- Boolean AdvanceToItem(const T&);
-
- const T& Current() const;
- void SetCurrent(const T& newValue);
- void RemoveCurrent();
-
- virtual void NotifyItemAdded(SInt32 indexOfNewItem);
- virtual void NotifyItemRemoved(SInt32 indexOfItemRemoved);
- virtual void NotifyListDestroyed();
-
- private:
- AListOf<T>* fList;
- SInt32 fCurrentItem;
- Boolean fRemovedCurrent;
- Boolean fWeRemovedCurrent;
- Boolean fIterateBackwards;
- };
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::Reset
- //-------------------------------------------------------------------
- template <class T>
- void AnIteratorOfAListOf<T>::Reset(Boolean iterateBackwards)
- {
- if(fList != nil)
- {
- fList->LockForReading();
- fIterateBackwards = iterateBackwards;
-
- if(fIterateBackwards)
- fCurrentItem = fList->ItemsInList() - 1;
- else
- fCurrentItem = 0;
- fList->RelinquishReadLock();
- }
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::More
- //-------------------------------------------------------------------
- template <class T>
- Boolean AnIteratorOfAListOf<T>::More() const
- {
- Boolean moreItems = false;
-
- if(fList != nil)
- {
- fList->LockForReading();
- moreItems = (fCurrentItem < fList->ItemsInList()) && (fCurrentItem >= 0);
- fList->RelinquishReadLock();
- }
-
- return moreItems;
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::ItemsRemainingToIterate
- //-------------------------------------------------------------------
- template <class T>
- UInt32 AnIteratorOfAListOf<T>::ItemsRemainingToIterate() const
- {
- UInt32 remainingItems = 0;
-
- if(fList != nil)
- {
- if(fIterateBackwards)
- remainingItems = fCurrentItem + 1;
- else
- {
- fList->LockForReading();
- SInt32 totalItems = fList->ItemsInList();
- fList->RelinquishReadLock();
-
- remainingItems = totalItems - fCurrentItem;
- }
- }
-
- return remainingItems;
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::Next
- //-------------------------------------------------------------------
- template <class T>
- void AnIteratorOfAListOf<T>::Next()
- {
- if(fList != nil)
- {
- //
- // We must lock for reading so that someone does not
- // come along and change the list (modifying our
- // fCurrentItem) while we are updating our iteration
- // state.
- //
- fList->LockForReading();
- if((fRemovedCurrent == false) && (this->More()))
- {
- if(fIterateBackwards)
- --fCurrentItem;
- else
- ++fCurrentItem;
- }
- fRemovedCurrent = false;
- fList->RelinquishReadLock();
- }
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::AdvanceToItem
- //
- // n.b. If Current() == itemToFind, then this routine will NOT
- // advance anywhere, so cal Next() between calls to AdvanceToItem()
- // if you need to find every item of a given value in a list.
- //
- // fCurrentItem starts at the first item in the list, so this
- // routine wouldn't be able to find the first item in a list
- // if it skipped the current item before searching.
- //-------------------------------------------------------------------
- template <class T>
- Boolean AnIteratorOfAListOf<T>::AdvanceToItem(const T& itemToFind)
- {
- Boolean foundItem = false;
-
- if(fList != nil)
- {
- if(fIterateBackwards == true)
- {
- DebugStr("\pAdvanceToItem doesn't work right when iterating backwards. switching to forward iteration");
- this->Reset(false);
- }
-
- fList->LockForReading();
- SInt32 foundIndex = fList->IndexOfItem(itemToFind, fCurrentItem);
- if(foundIndex != -1)
- {
- fCurrentItem = foundIndex;
- foundItem = true;
- }
- fList->RelinquishReadLock();
- }
-
- return foundItem;
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::Current
- //-------------------------------------------------------------------
- template <class T>
- const T& AnIteratorOfAListOf<T>::Current() const
- {
- T result;
-
- if(fList != nil)
- {
- //
- // We must lock for reading so that someone does not
- // change the list in between the time we access our
- // field fCurrentItem and the time that ItemAtIndex
- // returns.
- //
- fList->LockForReading();
- result = fList->ItemAtIndex(fCurrentItem);
- fList->RelinquishReadLock();
- }
-
- return result;
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::SetCurrent
- //-------------------------------------------------------------------
- template <class T>
- void AnIteratorOfAListOf<T>::SetCurrent(const T& newValue)
- {
- if(fList != nil)
- {
- fList->LockForWriting();
- fList->ReplaceItemAtIndex(fCurrentItem, newValue);
- fList->RelinquishWriteLock();
- }
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::RemoveCurrent
- //-------------------------------------------------------------------
- template <class T>
- void AnIteratorOfAListOf<T>::RemoveCurrent()
- {
- if(this->More())
- {
- //
- // When we call 'RemoveItemAtIndex,' we
- // will be called back and our fCurrentItem
- // will be automatically updated, and
- // fRemovedCurrent will be set to true.
- //
- // The same thing would happen if someone
- // else removes our current item.
- //
- fList->LockForWriting();
- fList->RemoveItemAtIndex(fCurrentItem);
- fList->RelinquishWriteLock();
-
- fWeRemovedCurrent = true;
- }
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::NotifyItemAdded
- //-------------------------------------------------------------------
- template <class T>
- void AnIteratorOfAListOf<T>::NotifyItemAdded(SInt32 indexOfNewItem)
- {
- //
- // If an item is inserted before our current item,
- // then we want to advance such that 'fCurrentItem'
- // still points at the same item it did before the
- // insertion happened.
- //
- if(indexOfNewItem <= fCurrentItem)
- ++fCurrentItem;
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::NotifyItemRemoved
- //-------------------------------------------------------------------
- template <class T>
- void AnIteratorOfAListOf<T>::NotifyItemRemoved(SInt32 indexOfItemRemoved)
- {
- //
- // If someone removes our current item, then
- // we need to adjust for that fact.
- //
- if(indexOfItemRemoved == fCurrentItem)
- {
- //
- // Immediately adjust 'fCurrentItem' so that
- // it points to the next item, and remember
- // that the current item was removed so that
- // Next() will not advance again.
- //
- if(fIterateBackwards)
- --fCurrentItem;
- fRemovedCurrent = true;
- fWeRemovedCurrent = false;
- }
- //
- // If someone removes an item that is not our current
- // item, then adjust 'fCurrentItem' such that it still
- // points at the same item it did before the removal.
- //
- else if(indexOfItemRemoved < fCurrentItem)
- {
- --fCurrentItem;
- }
- }
-
- //-------------------------------------------------------------------
- // AnIteratorOfAListOf<T>::NotifyListDestroyed
- //-------------------------------------------------------------------
- template <class T>
- void AnIteratorOfAListOf<T>::NotifyListDestroyed()
- {
- fList = nil;
- }
-
- #endif
-